class Solution {
public:
    int trap(vector<int>& height) {
        deque<int> que;
        int ans = 0;
        for (int i = 0; i < height.size(); i++) {
            while (!que.empty() && height[que.back()] < height[i]) {
                int top = que.back();
                que.pop_back();
                if (que.empty()) { break; }
                int left = que.back();
                int currWeight = i - left - 1;
                int currHigh = min(height[left], height[i]) - height[top];
                ans += currHigh * currWeight;
            }
            que.push_back(i);
        }
        return ans;
    }
}
